package com.hanxiaozhang.no10leetcode.array;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 假设一个升序排列的数组，以某个未知元素为轴旋转。例如，[0,1,2,4,5,6,7]变成了[4,5,6,7,0,1,2]。
 * 然后会给你一个目标元素在数组中进行搜索，如果存在则返回数组下标，如果不存在则返回-1。
 * 你可以认为数组中没有重复数字，算法的时间复杂度为O(log n)。
 * 实例 1:
 * 输入: arr = [4,5,6,7,0,1,2], target = 0
 * 输出: 4
 * <p>
 * 实例 2:
 * 输入: arr = [4,5,6,7,0,1,2], target = 3
 * 输出: -1
 * <p>
 * 思路：二分查找法的变种
 * 二分法的在获得了中间数后，需要判断下面搜索左半段还是右半段，通过找规律：
 * 如果中间的数小于最右边的数，则右半段是有序的；如果中间数大于最右边的数，则左半段是有序的。
 * 然后，在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，这样就可以确定二分法接下来搜索那半段。
 *
 * @author hanxinghua
 * @create 2024/1/10
 * @since 1.0.0
 */
public class No33SearchInRotatedSortedArray {

    public static void main(String[] args) {

        int[] arr = {4, 5, 6, 7, 0, 1, 2};
        int target = 4;
        System.out.println(method1(arr, target));
    }


    /**
     * 方法1：二分查找法的变种
     * <p>
     * 参考文章：https://www.jianshu.com/p/895f216c235f
     * <p>
     * 找规律（这个最难了）：
     * 二分法的在获得了中间数后，需要判断下面搜索左半段还是右半段，通过找规律：
     * 如果中间的数小于最右边的数，则右半段是有序的；如果中间数大于最右边的数，则左半段是有序的。
     * 然后，在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，这样就可以确定二分法接下来搜索那半段。
     *
     * @param arr
     * @param target
     * @return
     */
    private static int method1(int[] arr, int target) {

        int left = 0, right = arr.length - 1, mid = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (arr[mid] == target) {
                return mid;
            }
            //  中间的值 < 右边界值   -> 推理出：右侧数据是连续升序
            else if (arr[mid] < arr[right]) {
                // arr[mid] < target <= arr[right] ->  右侧数据是连续升序 && 目标值在右侧范围内 ，去右侧搜索，否则去左侧搜索
                if (target > arr[mid] && target <= arr[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {   // 中间的值 > 右边界值   -> 推理出：左侧数据是连续升序
                // arr[left] < target <= arr[mid] ->  左侧数据是连续升序 && 目标值在左侧范围内 ，去左侧搜索，否则去右侧搜索
                if (target >= arr[left] && target < arr[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }

        return -1;
    }

}
